{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Divide Array Into Increasing Sequences"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: canDivideIntoSubsequences"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #将数组分成几个递增序列"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个 <strong>非递减</strong> 的正整数数组&nbsp;<code>nums</code>&nbsp;和整数&nbsp;<code>K</code>，判断该数组是否可以被分成一个或几个&nbsp;<strong>长度至少&nbsp;为 </strong><code>K</code><strong> 的 不相交的递增子序列</strong>。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>nums = [1,2,2,3,3,4,4], K = 3\n",
    "<strong>输出：</strong>true\n",
    "<strong>解释：</strong>\n",
    "该数组可以分成两个子序列 [1,2,3,4] 和 [2,3,4]，每个子序列的长度都至少是 3。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>nums = [5,6,6,7,8], K = 3\n",
    "<strong>输出：</strong>false\n",
    "<strong>解释：</strong>\n",
    "没有办法根据条件来划分数组。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ol>\n",
    "\t<li><code>1 &lt;= nums.length&nbsp;&lt;= 10^5</code></li>\n",
    "\t<li><code>1 &lt;= K &lt;= nums.length</code></li>\n",
    "\t<li><code>1 &lt;= nums[i] &lt;= 10^5</code></li>\n",
    "</ol>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [divide-array-into-increasing-sequences](https://leetcode.cn/problems/divide-array-into-increasing-sequences/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [divide-array-into-increasing-sequences](https://leetcode.cn/problems/divide-array-into-increasing-sequences/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,2,3,3,4,4]\\n3', '[5,6,6,7,8]\\n3']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canDivideIntoSubsequences(self, nums: List[int], k: int) -> bool:\n",
    "        pre = nums[0]\n",
    "        cnt = 0\n",
    "        for n in nums:\n",
    "            if pre == n:\n",
    "                cnt += 1\n",
    "            else:\n",
    "                pre = n\n",
    "                cnt = 1\n",
    "            if cnt * k > len(nums):\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canDivideIntoSubsequences(self, nums: List[int], k: int) -> bool:\n",
    "      maxCnt = 0\n",
    "      L = i = 0\n",
    "      n = len(nums)\n",
    "      while i < n:\n",
    "        while i + 1 < n and nums[i + 1] == nums[i]:\n",
    "          i += 1\n",
    "        \n",
    "        maxCnt = max(maxCnt, i - L + 1)\n",
    "        L = i = i + 1\n",
    "      return n >= k * maxCnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canDivideIntoSubsequences(self, nums: List[int], k: int) -> bool:\n",
    "      maxCnt = 0\n",
    "      L = i = 0\n",
    "      n = len(nums)\n",
    "      while i < n:\n",
    "        while i + 1 < n and nums[i + 1] == nums[i]:\n",
    "          i += 1\n",
    "        \n",
    "        maxCnt = max(maxCnt, i - L + 1)\n",
    "        L = i = i + 1\n",
    "      return n >= k * maxCnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canDivideIntoSubsequences(self, nums: List[int], k: int) -> bool:\n",
    "        # 如果可以划分\n",
    "        # 那么对于重复的数字，在每个序列中只出现一次\n",
    "        return max(Counter(nums).values())*k <= len(nums)\n",
    "\n",
    " "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canDivideIntoSubsequences(self, nums: List[int], k: int) -> bool:\n",
    "        return k * max(Counter(nums).values()) <= len(nums)  # 需要的序列就是这么多个 也就是最大频率个"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canDivideIntoSubsequences(self, nums: List[int], k: int) -> bool:\n",
    "        cnt = Counter(nums)\n",
    "        mx_cnt = max(cnt.values())\n",
    "        return mx_cnt * k <= len(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canDivideIntoSubsequences(self, nums: List[int], k: int) -> bool:\n",
    "        return max(Counter(nums).values()) * k <= len(nums)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canDivideIntoSubsequences(self, nums: List[int], k: int) -> bool:\n",
    "      numCountMap = collections.defaultdict(int)\n",
    "      maxCount = 0\n",
    "      n = len(nums)\n",
    "      for num in nums:\n",
    "        numCountMap[num] += 1\n",
    "        maxCount = max(maxCount, numCountMap[num])\n",
    "      return n//maxCount >= k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canDivideIntoSubsequences(self, nums: List[int], k: int) -> bool:\n",
    "        return max(Counter(nums).values())*k<=len(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canDivideIntoSubsequences(self, nums: List[int], k: int) -> bool:\n",
    "        v1 = Counter(nums)\n",
    "        v2 = max(v1.values())\n",
    "        return v2 * k <= len(nums)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canDivideIntoSubsequences(self, nums: List[int], k: int) -> bool:\n",
    "        c=Counter(nums)\n",
    "        ma=max(c.values())\n",
    "        return len(nums)//ma>=k\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canDivideIntoSubsequences(self, nums: List[int], k: int) -> bool:\n",
    "        cnt = Counter(nums)\n",
    "        return max(cnt.values())*k <= len(nums)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
